package MinLoad;

import java.util.LinkedList;
import java.util.Queue;

public class NearestExit {
    boolean[][] vis = new boolean[101][101];
    int m, n;
    int[] dx = new int[]{0, 0, -1, 1};
    int[] dy = new int[]{1, -1, 0, 0};

    public int code(char[][] maze, int[] entrance) {
        m = maze.length;
        n = maze[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{entrance[0], entrance[1]});
        vis[entrance[0]][entrance[1]] = true;
        int ret = 0;

        while(!q.isEmpty()){
            ret++;
            int sz = q.size();

            for(int i = 0; i < sz; i++)
            {
                int[] t = q.poll();
                int a = t[0], b = t[1];

                for(int j = 0; j < 4; j++){
                    int x = a + dx[j], y = b + dy[j];

                    if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' & !vis[x][y]){
                        // 判断是否已经到出⼝
                        if(x == 0 || x == m - 1 || y == 0 || y == n - 1) {
                            return ret;
                        }

                        vis[x][y] = true;
                        q.add(new int[]{x, y});
                    }
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        NearestExit test = new NearestExit();
//        char[][] n = new char[][]{{'+','.', '+','+','+', '+', '+'},{'+','.','+','.','.', '.', '+'},
//                {'+','.', '+','.','+', '.', '+'},{'+','.', '.','.','.', '.', '+'},
//                {'+','+', '+','+','.', '+', '.'}};
//        int[] e = new int[]{0, 1};

        char[][] n = new char[][]{{'+','+', '.','+'},{'.','.', '.','+'},
                {'+','+', '+','.'}};
        int[] e = new int[]{1, 2};
        test.code(n, e);
        //test.code();
    }
}
